{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of People Aware of a Secret"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #queue #dynamic-programming #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #队列 #动态规划 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: peopleAwareOfSecret"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #知道秘密的人数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>在第 <code>1</code>&nbsp;天，有一个人发现了一个秘密。</p>\n",
    "\n",
    "<p>给你一个整数&nbsp;<code>delay</code>&nbsp;，表示每个人会在发现秘密后的 <code>delay</code>&nbsp;天之后，<strong>每天</strong>&nbsp;给一个新的人&nbsp;<strong>分享</strong>&nbsp;秘密。同时给你一个整数&nbsp;<code>forget</code>&nbsp;，表示每个人在发现秘密&nbsp;<code>forget</code>&nbsp;天之后会&nbsp;<strong>忘记</strong>&nbsp;这个秘密。一个人&nbsp;<strong>不能</strong>&nbsp;在忘记秘密那一天及之后的日子里分享秘密。</p>\n",
    "\n",
    "<p>给你一个整数&nbsp;<code>n</code>&nbsp;，请你返回在第 <code>n</code>&nbsp;天结束时，知道秘密的人数。由于答案可能会很大，请你将结果对&nbsp;<code>10<sup>9</sup> + 7</code>&nbsp;<strong>取余</strong>&nbsp;后返回。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>n = 6, delay = 2, forget = 4\n",
    "<b>输出：</b>5\n",
    "<strong>解释：</strong>\n",
    "第 1 天：假设第一个人叫 A 。（一个人知道秘密）\n",
    "第 2 天：A 是唯一一个知道秘密的人。（一个人知道秘密）\n",
    "第 3 天：A 把秘密分享给 B 。（两个人知道秘密）\n",
    "第 4 天：A 把秘密分享给一个新的人 C 。（三个人知道秘密）\n",
    "第 5 天：A 忘记了秘密，B 把秘密分享给一个新的人 D 。（三个人知道秘密）\n",
    "第 6 天：B 把秘密分享给 E，C 把秘密分享给 F 。（五个人知道秘密）\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>n = 4, delay = 1, forget = 3\n",
    "<b>输出：</b>6\n",
    "<strong>解释：</strong>\n",
    "第 1 天：第一个知道秘密的人为 A 。（一个人知道秘密）\n",
    "第 2 天：A 把秘密分享给 B 。（两个人知道秘密）\n",
    "第 3 天：A 和 B 把秘密分享给 2 个新的人 C 和 D 。（四个人知道秘密）\n",
    "第 4 天：A 忘记了秘密，B、C、D 分别分享给 3 个新的人。（六个人知道秘密）\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= n &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= delay &lt; forget &lt;= n</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-people-aware-of-a-secret](https://leetcode.cn/problems/number-of-people-aware-of-a-secret/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-people-aware-of-a-secret](https://leetcode.cn/problems/number-of-people-aware-of-a-secret/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['6\\n2\\n4', '4\\n1\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "        humans = [0]*forget\n",
    "        humans[-1] = 1\n",
    "        for i in range(n-1):\n",
    "            humans.pop(0)\n",
    "            humans.append(sum(humans[:forget-delay])%(1e9 + 7))\n",
    "        return int(sum(humans)%(1e9 + 7))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "        # 1 刷表法： 用当前状态更新其他状态\n",
    "        # MOD = 10 ** 9 + 7\n",
    "        # f = [0] * n # f[i] 第i天可以通知秘密的人数\n",
    "        # f[0] = 1\n",
    "        # cnt_b = 0 # 不能通知秘密的人数\n",
    "        # for i, v in enumerate(f):\n",
    "        #     if i + delay >= n:\n",
    "        #         cnt_b += v\n",
    "        #     for j in range(i + delay, min(i + forget, n)): # 把一段区间都加上同一个数的操作可以用差分实现\n",
    "        #         f[j] = (f[j] + v) % MOD \n",
    "        # return (f[-1] + cnt_b) % MOD\n",
    "\n",
    "        # 2. 填表法：用其他状态更新当前状态\n",
    "        MOD = 10 ** 9 + 7\n",
    "        sum = [0] * (n + 1)\n",
    "        sum[1] = 1\n",
    "        for i in range(2, n + 1):\n",
    "            f = sum[max(i - delay, 0)] - sum[max(i - forget, 0)]\n",
    "            sum[i] = (sum[i - 1] + f) % MOD\n",
    "        return (sum[n] - sum[max(n - forget, 0)]) % MOD\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        f = [0] * n\n",
    "        f[0] = 1\n",
    "        cnt_b = 0\n",
    "        for i, v in enumerate(f):\n",
    "            if i + delay >= n:\n",
    "                cnt_b += v\n",
    "            for j in range(i + delay, min(i + forget, n)):\n",
    "                f[j] = (f[j] + v) % MOD\n",
    "        return (f[-1] + cnt_b) % MOD\n",
    "\n",
    "\n",
    "        MOD = 10 ** 9 + 7\n",
    "        diff = [0] * n\n",
    "        diff[0] = 1  # f[0] = 1，相当于 diff[0] = 1, diff[1] = -1\n",
    "        diff[1] = -1\n",
    "        f = cnt_b = 0\n",
    "        for i, d in enumerate(diff):\n",
    "            f = (f + d) % MOD\n",
    "            if i + delay >= n:\n",
    "                cnt_b += f\n",
    "            else:\n",
    "                diff[i + delay] += f\n",
    "                if i + forget < n:\n",
    "                    diff[i + forget] -= f\n",
    "        return (f + cnt_b) % MOD\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "        dp = [0] * 1001 # people who could share secret\n",
    "        dp[1] = 1\n",
    "        cnt = 0\n",
    "        for i in range(1, n+1):\n",
    "            if i+delay > n:\n",
    "                cnt += dp[i]\n",
    "                cnt %= (10**9+7)\n",
    "            for j in range(i+delay, min(i+forget, n+1)):\n",
    "                dp[j] += dp[i]\n",
    "                dp[j] %= (10**9+7)\n",
    "        return (dp[n] + cnt) % (10**9+7)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "\n",
    "        MOD=10**9+7\n",
    "        dp=[0]*n\n",
    "        dp[0]=1\n",
    "        cnt=0\n",
    "        for idx,val in enumerate(dp):\n",
    "            if idx+delay>=n:\n",
    "                cnt+=val\n",
    "            for j in range(idx+delay,min(idx+forget,n)):\n",
    "                dp[j]=(dp[j]+val)%MOD\n",
    "        return (dp[-1]+cnt)%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "    dp = [0]* n\n",
    "    dp[0] = 1\n",
    "    m = 10 ** 9 + 7\n",
    "    for i in range(n - delay):\n",
    "      if dp[i] > 0:\n",
    "        for j in range(i + delay, min(i + forget, n)):\n",
    "          dp[j] = (dp[j] + dp[i]) % m\n",
    "        # print(f\"{i} dp {dp}\")\n",
    "    return sum(dp[n - forget:]) % m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "        mod = 1e9 + 7\n",
    "        humans = [0]*forget\n",
    "        humans[-1] = 1\n",
    "        for i in range(n-1):\n",
    "            humans.pop(0)\n",
    "            humans.append(sum(humans[:forget-delay])%mod)\n",
    "        return int(sum(humans)%mod)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "\n",
    "        MOD = 10 ** 9 + 7\n",
    "\n",
    "        f = [0] * n\n",
    "\n",
    "        f[0] = 1\n",
    "\n",
    "        cnt_b = 0\n",
    "\n",
    "        for i, v in enumerate(f):\n",
    "\n",
    "            if i + delay >= n:\n",
    "\n",
    "                cnt_b += v\n",
    "\n",
    "            for j in range(i + delay, min(i + forget, n)):\n",
    "\n",
    "                f[j] = (f[j] + v) % MOD\n",
    "\n",
    "        return (f[-1] + cnt_b) % MOD\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "        dp = [0] * (n+1) # people who could share secret\n",
    "        dp[1] = 1\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(i+delay, min(i+forget, n+1)):\n",
    "                dp[j] += dp[i]\n",
    "                dp[j] %= (10**9+7)\n",
    "        print(dp)\n",
    "        return sum(dp[-forget:]) % (10**9+7)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        diff = [0] * n\n",
    "        diff[0] = 1  # f[0] = 1，相当于 diff[0] = 1, diff[1] = -1\n",
    "        diff[1] = -1\n",
    "        f = cnt_b = 0\n",
    "        for i, d in enumerate(diff):\n",
    "            f = (f + d) % MOD\n",
    "            if i + delay >= n:\n",
    "                cnt_b += f\n",
    "            else:\n",
    "                diff[i + delay] += f\n",
    "                if i + forget < n:\n",
    "                    diff[i + forget] -= f\n",
    "        return (f + cnt_b) % MOD\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        f = [0] * n\n",
    "        f[0] = 1\n",
    "        cnt_b = 0\n",
    "        for i, v in enumerate(f):\n",
    "            if i + delay >= n:\n",
    "                cnt_b += v\n",
    "            for j in range(i + delay, min(i + forget, n)):\n",
    "                f[j] = (f[j] + v) % MOD\n",
    "        return (f[-1] + cnt_b) % MOD\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "        mod=10**9+7\n",
    "        dp=[0]*(n+1)\n",
    "        dp[1]=1\n",
    "        res=0\n",
    "        for i in range(1,n+1):\n",
    "            if i+delay<(n+1):\n",
    "                for j in range(i+delay,min(i+forget,n+1)):\n",
    "                    dp[j]=(dp[j]+dp[i])%mod\n",
    "            else:\n",
    "                res=(res+dp[i])%mod\n",
    "       # print(dp[-forget:])\n",
    "        #print(res)\n",
    "        return (dp[-1]+res)%mod\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "        x = [0]*(n+1)\n",
    "        y = [0]*(n+1)\n",
    "        z = [0]*(n+1)\n",
    "        x[1] = 1\n",
    "        y[1] = z[1] = 0\n",
    "        for i in range(2,n+1):\n",
    "            if i>=delay+1:\n",
    "                y[i] = x[i-delay]\n",
    "            if i>forget:\n",
    "                z[i] = x[i-forget]\n",
    "            x[i] = x[i-1]-z[i]+y[i]\n",
    "        return (x[-1]-z[-1])%(10**9+7)\n",
    "        # q = deque()\n",
    "        # q.append([forget,delay])\n",
    "        # res = 1\n",
    "        # for i in range(1,n):\n",
    "        #     t = len(q)\n",
    "        #     for j in range(t):\n",
    "        #         q[j][0] -= 1\n",
    "        #         q[j][1] -= 1\n",
    "        #     if q[0][0] <= 0:\n",
    "        #         q.popleft()\n",
    "        #     t = len(q)\n",
    "        #     for j in range(t):\n",
    "        #         if q[j][1]<=0:\n",
    "        #             q.append([forget,delay])\n",
    "                    \n",
    "        # return len(q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        f = [0] * n\n",
    "        f[0] = 1\n",
    "        cnt_b = 0\n",
    "        for i, v in enumerate(f):\n",
    "            if i + delay >= n:\n",
    "                cnt_b += v\n",
    "            for j in range(i + delay, min(i + forget, n)):\n",
    "                f[j] = (f[j] + v) % MOD\n",
    "        return (f[-1] + cnt_b) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "        d = [0] * forget\n",
    "        d[0] = 1\n",
    "        for i in range(n-1):\n",
    "            d = [0] + d[:-1]\n",
    "            d[0] = sum(d[delay:]) % 1000000007\n",
    "        return (sum(d) % 1000000007)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        \n",
    "        f = [0] * (n + 1)\n",
    "        g = [0] * (n + 1)\n",
    "        f[1] = 1\n",
    "        g[1] = 1\n",
    "\n",
    "        for i in range(2, n+1):\n",
    "            l = max(0, i - forget)\n",
    "            r = max(0, i - delay)\n",
    "            f[i] = (g[r] - g[l] + mod) % mod\n",
    "            g[i] = (g[i-1] + f[i]) % mod\n",
    "        \n",
    "        return (g[n] - g[max(0, n - forget)] + mod) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "        # 1 刷表法： 用当前状态更新其他状态\n",
    "        MOD = 10 ** 9 + 7\n",
    "        f = [0] * n # f[i] 第i天可以通知秘密的人数\n",
    "        f[0] = 1\n",
    "        cnt_b = 0 # 不能通知秘密的人数\n",
    "        for i, v in enumerate(f):\n",
    "            if i + delay >= n:\n",
    "                cnt_b += v\n",
    "            for j in range(i + delay, min(i + forget, n)): # 把一段区间都加上同一个数的操作可以用差分实现\n",
    "                f[j] = (f[j] + v) % MOD \n",
    "        return (f[-1] + cnt_b) % MOD\n",
    "\n",
    "        # 2. 填表法：用其他状态更新当前状态\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "        MOD = 10**9+7\n",
    "        f = [0] * n\n",
    "        f[0] = 1\n",
    "        cnt_b = 0\n",
    "        for i, cnt_a in enumerate(f):\n",
    "            if i + delay >= n:\n",
    "                cnt_b += cnt_a\n",
    "            for j in range(i+delay, min(i+forget, n)):\n",
    "                f[j] = (f[j] + cnt_a) % MOD\n",
    "        return (f[-1] + cnt_b) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "        #带延时的滑动窗口\n",
    "        dp = [0]*n\n",
    "        dp[0] = 1\n",
    "        #p为滑动窗口缓存\n",
    "        p = 0\n",
    "        l = -delay\n",
    "        r = -forget\n",
    "        for i in range(delay,n):\n",
    "            p += dp[i-delay]\n",
    "            if i - forget >= 0:\n",
    "                p -= dp[i-forget]\n",
    "            dp[i] = p\n",
    "        return sum(dp[n-forget:n]) % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "        humans = [0]*forget\n",
    "        humans[-1] = 1\n",
    "        for i in range(n-1):\n",
    "            humans.pop(0)\n",
    "            humans.append(sum(humans[:forget-delay])%(1e9 + 7))\n",
    "        return int(sum(humans)%(1e9 + 7))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "        l = [0]*forget + [1]\n",
    "        for i in range(n-1):\n",
    "            l.append(sum(l[-forget+1:len(l)-delay+1]))\n",
    "        return sum(l[-forget:])%1000000007\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "        c, m = Counter([0]), 10 ** 9 + 7\n",
    "        for i in range(delay, n):\n",
    "            j = i - forget\n",
    "            if j in c:\n",
    "                del c[j]\n",
    "            j = i - delay\n",
    "            c[i] = sum(c[k] for k in c if k <= j) % m\n",
    "        return sum(c.values()) % m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "          \n",
    "        mod = 1000000007\n",
    "        dp=[0]*(n+1)\n",
    "        dp[1]=1\n",
    "        ans=0\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(i+delay,min(i+forget-1,n)+1):\n",
    "                dp[j]+=dp[i]\n",
    "                dp[j]%=mod\n",
    "\n",
    "        for k in range(n-forget+1,n+1):\n",
    "            ans+=dp[k]\n",
    "            ans%=mod\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "\n",
    "        mod = 10 ** 9 + 7\n",
    "        f = [0] * (n + 1)\n",
    "        g = [0] * (n + 1)\n",
    "        f[1], g[1] = 1, 1\n",
    "\n",
    "\n",
    "        for i in range(2, n+1):\n",
    "            left = max(0, i - forget)\n",
    "            right = max(0, i - delay)\n",
    "            f[i] = (g[right] - g[left] + mod) % mod\n",
    "            g[i] = (g[i-1] + f[i]) % mod\n",
    "\n",
    "        ans = (g[n] - g[max(0, n-forget)] + mod) % mod\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "        dp = [0] * n\n",
    "        dp[0] = 1\n",
    "        MOD = 10**9+7\n",
    "        add = [0] * n\n",
    "        add[0] = 1\n",
    "        for i in range(1, n):\n",
    "            dp[i] = dp[i-1]\n",
    "            if i-delay>=0:\n",
    "                sm = sum(add[max(0, i-forget+1):i-delay+1]) % MOD\n",
    "                add[i] = sm\n",
    "            dp[i] = (dp[i]+add[i]) % MOD\n",
    "            if i>=forget:\n",
    "                dp[i]-=add[i-forget]\n",
    "        return dp[n-1] % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "        dp = [0] * (n+1) # people who could share secret\n",
    "        dp[1] = 1\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(i+delay, min(i+forget, n+1)):\n",
    "                dp[j] += dp[i]\n",
    "                dp[j] %= (10**9+7)\n",
    "        return (dp[n]+sum(dp[-delay:])) % (10**9+7)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "        humans = [0]*forget\n",
    "        humans[-1] = 1\n",
    "        for i in range(n-1):\n",
    "            humans.pop(0)\n",
    "            humans.append(sum(humans[:forget-delay])%(1e9 + 7))\n",
    "        return int(sum(humans)%(1e9 + 7))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "        #1 2 1 1\n",
    "        new_people_list = [0 for _ in range(forget)]\n",
    "        new_cnt = 0\n",
    "        new_people_list[0] = 1\n",
    "        for idx in range(1, n):\n",
    "            idx = idx % forget\n",
    "            new_cnt -= new_people_list[idx]\n",
    "            idy = (idx - delay) % forget\n",
    "            new_cnt += new_people_list[idy]\n",
    "            new_cnt %= (10**9 + 7)\n",
    "            new_people_list[idx] = new_cnt\n",
    "        return sum(new_people_list) % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "        # A类人：可以传播的人\n",
    "        # B类人：知道但是不能传播的人\n",
    "        # C类人：已经忘记的人，也不能继续知道\n",
    "        MOD = 10 ** 9 + 7\n",
    "        f = [0] * n # f[i]表示第i天A类人的数量\n",
    "        f[0] = 1\n",
    "        cnt_b = 0\n",
    "        for i, v in enumerate(f):\n",
    "            if i + delay >= n:\n",
    "                cnt_b += v # 如果当前天数到结束都没超过delay里，最终就会b类人计入答案。\n",
    "            for j in range(i+delay, min(i + forget, n)):\n",
    "                f[j] = (f[j] + v) % MOD \n",
    "        return (f[-1] + cnt_b) % MOD\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "        dp = [0] * 1001 # people who could share secret\n",
    "        dp[1] = 1\n",
    "        cnt = 0\n",
    "        for i in range(1, n+1):\n",
    "            if i+delay > n:\n",
    "                cnt += dp[i]\n",
    "                cnt %= (10**9+7)\n",
    "            for j in range(i+delay, i+forget):\n",
    "                if j>n:\n",
    "                    break\n",
    "                dp[j] += dp[i]\n",
    "                dp[j] %= (10**9+7)\n",
    "        return (dp[n] + cnt) % (10**9+7)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "        mod = 1e9 + 7\n",
    "        humans = [0]*forget\n",
    "        humans[-1] = 1\n",
    "        for i in range(n-1):\n",
    "            humans.pop(0)\n",
    "            humans.append(sum(humans[:forget-delay])%mod)\n",
    "        return int(sum(humans)%mod)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "        x = [0]*(n+1)\n",
    "        y = [0]*(n+1)\n",
    "        z = [0]*(n+1)\n",
    "        x[1] = 1\n",
    "        y[1] = z[1] = 0\n",
    "        for i in range(2,n+1):\n",
    "            if i>=delay+1:\n",
    "                y[i] = x[i-delay]\n",
    "            if i>forget:\n",
    "                z[i] = x[i-forget]\n",
    "            x[i] = x[i-1]-z[i]+y[i]\n",
    "        return (x[-1]-z[-1])%(10**9+7)\n",
    "        # q = deque()\n",
    "        # q.append([forget,delay])\n",
    "        # res = 1\n",
    "        # for i in range(1,n):\n",
    "        #     t = len(q)\n",
    "        #     for j in range(t):\n",
    "        #         q[j][0] -= 1\n",
    "        #         q[j][1] -= 1\n",
    "        #     if q[0][0] <= 0:\n",
    "        #         q.popleft()\n",
    "        #     t = len(q)\n",
    "        #     for j in range(t):\n",
    "        #         if q[j][1]<=0:\n",
    "        #             q.append([forget,delay])\n",
    "                    \n",
    "        # return len(q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "        def dfs(i):\n",
    "            if i <= delay:\n",
    "                return [0] * (i - 1) + [1] + [0] * (forget - i)\n",
    "\n",
    "            d = dfs(i - 1)\n",
    "            d.pop()\n",
    "            d.insert(0, 0)\n",
    "            for j in d[delay:]:\n",
    "                d[0] += j\n",
    "            d[0] = int(d[0] % (1e9 + 7))\n",
    "            return d\n",
    "        f = [1] + [0] * (forget - 1)\n",
    "\n",
    "        for i in range(n - 1):\n",
    "            f.pop()\n",
    "            f.insert(0, 0)\n",
    "            for j in f[delay:]:\n",
    "                f[0] += j\n",
    "            f[0] = int(f[0] % (1e9 + 7))\n",
    "\n",
    "        # return int(sum(dfs(n)) % (1e9 + 7))\n",
    "        return int(sum(f) % (1e9 + 7))\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        f = [0] * n  # 初始化 f 数组\n",
    "        f[0] = 1  # 第一天有一个人知道秘密\n",
    "        cnt_b = 0  # 初始化 cnt_b\n",
    "        \n",
    "        for i, v in enumerate(f):\n",
    "            # 如果在第 n 天还不能分享秘密，更新 cnt_b\n",
    "            if i + delay >= n:\n",
    "                cnt_b += v\n",
    "            # 更新在第 i + delay 到 i + forget 天之间可以开始分享秘密的人数\n",
    "            for j in range(i + delay, min(i + forget, n)):\n",
    "                f[j] = (f[j] + v) % MOD  # 注意取模\n",
    "                \n",
    "        return (f[-1] + cnt_b) % MOD  # 注意取模\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "        my_mat=[0]*1001\n",
    "        my_mat[0]=1\n",
    "        for i in range(1,n):\n",
    "            # temp_forget=my_mat[forget-1]\n",
    "            new_num=0\n",
    "            for j in range(delay-1,forget-1):\n",
    "                new_num=new_num+my_mat[j]\n",
    "            # sum1=0\n",
    "            for j in range(forget-1,0,-1):\n",
    "                my_mat[j]=my_mat[j-1]\n",
    "                # sum1+=my_mat[j-1]\n",
    "            # sum1+=new_num\n",
    "            my_mat[0]=new_num%(10**9+7)\n",
    "            # sum1-=temp_forget\n",
    "\n",
    "        result=0\n",
    "        for i in range(forget):\n",
    "            result+=my_mat[i]\n",
    "\n",
    "        return result%(10**9+7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\r\n",
    "        MOD = 10 ** 9 + 7\r\n",
    "        diff = [0] * n\r\n",
    "        diff[0] = 1  # f[0] = 1，相当于 diff[0] = 1, diff[1] = -1\r\n",
    "        diff[1] = -1\r\n",
    "        f = cnt_b = 0\r\n",
    "        for i, d in enumerate(diff):\r\n",
    "            f = (f + d) % MOD\r\n",
    "            if i + delay >= n:\r\n",
    "                cnt_b += f\r\n",
    "            else:\r\n",
    "                diff[i + delay] += f\r\n",
    "                if i + forget < n:\r\n",
    "                    diff[i + forget] -= f\r\n",
    "        return (f + cnt_b) % MOD\r\n",
    "\r\n",
    "    # 填表法，（用其它状态计算当前状态）\r\n",
    "    def peopleAwareOfSecret2(self, n: int, delay: int, forget: int) -> int:\r\n",
    "        MOD = 10 ** 9 + 7\r\n",
    "        sum = [0] * (n + 1)\r\n",
    "        sum[1] = 1\r\n",
    "        for i in range(2, n + 1):\r\n",
    "            f = sum[max(i - delay, 0)] - sum[max(i - forget, 0)]\r\n",
    "            sum[i] = (sum[i - 1] + f) % MOD\r\n",
    "        return (sum[n] - sum[max(n - forget, 0)]) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "        dp=[0]*(n+1)\n",
    "        dp[1]=1\n",
    "       # for i in range(1,delay+1):\n",
    "        #    dp[i]=1\n",
    "        mod=10**9+7\n",
    "        cnt=0\n",
    "        for i in range(1,n+1):\n",
    "            if i+delay>=n+1:\n",
    "                cnt+=dp[i]\n",
    "            for j in range(i+delay,min(n+1,i+forget)):   \n",
    "                dp[j]=(dp[j]+dp[i])%mod\n",
    "\n",
    "        #print(dp)\n",
    "        return (dp[-1]+cnt)%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "        dp = [0] * 1001 # people who could share secret\n",
    "        dp[1] = 1\n",
    "        cnt = 0\n",
    "        for i in range(1, n+1):\n",
    "            if i+delay > n:\n",
    "                cnt += dp[i]\n",
    "                cnt %= (10**9+7)\n",
    "            for j in range(i+delay, i+forget):\n",
    "                try:\n",
    "                    dp[j] += dp[i]\n",
    "                    dp[j] %= (10**9+7)\n",
    "                except:\n",
    "                    break\n",
    "        print(dp)\n",
    "        return (dp[n] + cnt) % (10**9+7)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        dp = [0]*n\n",
    "        dp[0] = 1\n",
    "        pre = [0]*(n+1)\n",
    "        pre[1] = 1\n",
    "        for i in range(1, n):\n",
    "            low = i-forget+1\n",
    "            high = i-delay\n",
    "            if low < 0:\n",
    "                low = 0\n",
    "            if high < 0:\n",
    "                high = -1\n",
    "  \n",
    "            dp[i] = (pre[high+1] - pre[low])%mod\n",
    "            pre[i+1] = (pre[i]+dp[i]) % mod\n",
    "        return sum(dp[-forget:]) % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        dp = [0] * forget\n",
    "        dp[0] =1\n",
    "\n",
    "        ans = 1\n",
    "\n",
    "        for i in range(1,n):\n",
    "            new = 0\n",
    "            for j in range(delay-1,forget-1):\n",
    "                new += dp[j]\n",
    "            new =  new %MOD\n",
    "\n",
    "            ans = (ans +new -dp[-1])%MOD\n",
    "\n",
    "            for j in range(forget-1,0,-1):\n",
    "                dp[j] = dp[j-1]\n",
    "\n",
    "            dp[0] = new\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "        dp=[0]*(n+1)\n",
    "        dp[1]=1\n",
    "        mod=10**9+7\n",
    "        for i in range(2, n+1):\n",
    "            more=dp[max(i-delay,0)]-dp[max(i-forget,0)]\n",
    "            dp[i]=(dp[i-1]+more)%mod\n",
    "        return (dp[n]-dp[max(n-forget,0)])%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        diff = [0] * n\n",
    "        diff[0] = 1  # f[0] = 1，相当于 diff[0] = 1, diff[1] = -1\n",
    "        diff[1] = -1\n",
    "        f = cnt_b = 0\n",
    "        for i, d in enumerate(diff):\n",
    "            f = (f + d) % MOD\n",
    "            if i + delay >= n:\n",
    "                cnt_b += f\n",
    "            else:\n",
    "                diff[i + delay] += f\n",
    "                if i + forget < n:\n",
    "                    diff[i + forget] -= f\n",
    "        return (f + cnt_b) % MOD\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "        dp = [0]*n \n",
    "        dp[0] = 1\n",
    "        for i in range(n):\n",
    "            if(i+delay < n):\n",
    "                for j in range(i+delay,min(i+forget,n)):\n",
    "                    dp[j] += dp[i]\n",
    "        result = 0\n",
    "        for i in range(n-forget,n):\n",
    "            result += dp[i]\n",
    "        return result % (10**9+7)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        f = [0] * n\n",
    "        f[0] = 1\n",
    "        cnt_b = 0\n",
    "        for i, v in enumerate(f):\n",
    "            if i + delay >= n:\n",
    "                cnt_b += v\n",
    "            for j in range(i + delay, min(i + forget, n)):\n",
    "                f[j] = (f[j] + v) % MOD\n",
    "            \n",
    "        return (f[-1] + cnt_b) % MOD\n",
    "\n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "\n",
    "        f = [0] * (n + 1)\n",
    "        # 第i天可产生复利的人\n",
    "        f[1] = 1\n",
    "        cntb = 0\n",
    "        for i in range(1, n+1):\n",
    "            if i + delay > n:\n",
    "                cntb += f[i]\n",
    "                continue\n",
    "            for j in range(i+delay, min(n+1, i + forget)):\n",
    "                f[j] = (f[j] + f[i]) % mod\n",
    "        return (f[n] + cntb) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "\n",
    "        f = [0] * (n + 1)\n",
    "        # 第i天可产生复利的人\n",
    "        f[1] = 1\n",
    "        cntb = 0\n",
    "        for i in range(1, n+1):\n",
    "            if i + delay > n:\n",
    "                cntb += f[i]\n",
    "                continue\n",
    "            for j in range(i+delay, min(n, i + forget - 1) + 1):\n",
    "                f[j] = (f[j] + f[i]) % mod\n",
    "        return (f[n] + cntb) % mod\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "        a = []\n",
    "        for i in range(forget):\n",
    "            a.append(0)\n",
    "        x = 2\n",
    "        a[0] = 1\n",
    "        while x <= n:\n",
    "            for i in range(1,forget):\n",
    "                a[forget-i] = a[forget-i-1]\n",
    "            a[0] = 0\n",
    "            for i in range(delay,forget):\n",
    "                a[0] += a[i]\n",
    "            x += 1\n",
    "        return sum(a)%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        sm = [0] * (n+1)\n",
    "        sm[1:delay+1] = [1] * delay\n",
    "        for i in range(1+delay, n+1):\n",
    "            cur = sm[i-delay] - sm[max(i-forget,0)]\n",
    "            sm[i] = (sm[i-1] + cur) % MOD\n",
    "        return (sm[n] - sm[max(n-forget, 0)]) % MOD\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "        # 可分享人数\n",
    "        # 区分概念\n",
    "        # 知道的人数目  和 增加的 与减少的 分享人数目 \n",
    "        # \n",
    "        M = 10**9+7\n",
    "        know = [0]*(n+1)\n",
    "        diff = [0]*(n+1)\n",
    "        # 若 i 天 x 有人知道了， 则 i + d -> i + f 间 diff += x \n",
    "\n",
    "        know[1] = 1\n",
    "        if 1+ delay <= n:\n",
    "            diff[1 + delay] = 1\n",
    "        if 1 + forget <=n:\n",
    "            know[1+forget] -=1\n",
    "            diff[1+forget] -=1\n",
    "        \n",
    "        \n",
    "        for i in range(2, n+1):\n",
    "            diff[i] += diff[i-1]\n",
    "            # 今天分享的人\n",
    "            x = diff[i]\n",
    "            # 那么今天知道的新增为x\n",
    "            know[i]+= know[i-1]+x\n",
    "            if i + forget <=n:\n",
    "                know[i+forget] -= x\n",
    "            # 这些新增的人在i + delay 可以开始分享\n",
    "            if i + delay <= n:\n",
    "                diff[i+delay]+=x\n",
    "                if i+forget<= n:\n",
    "                    diff[i+forget] -=x\n",
    "            \n",
    "        return know[-1]%M\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "        mod=10**9+7\n",
    "        ans=deque([0]*forget)\n",
    "        ans[0]=1\n",
    "        if delay>1:\n",
    "            s=0\n",
    "        else:\n",
    "            s=1\n",
    "        for i in range(n-1):\n",
    "            s-=ans[-1]\n",
    "            ans.appendleft(s)\n",
    "            s+=ans[delay-1]\n",
    "            s%=mod\n",
    "            ans.pop()\n",
    "        return sum(ans)%mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "        dp=[0]*n\n",
    "        dp[0]=1\n",
    "        mod=10**9+7\n",
    "        ret=0\n",
    "        for i in range(1,n):\n",
    "            for j in range(i-forget+1,i-delay+1):\n",
    "                if j<0:\n",
    "                    continue\n",
    "                dp[i]+=dp[j]\n",
    "                dp[i]%=mod\n",
    "        for i in range(n-1,n-forget-1,-1):\n",
    "            if i>=0:\n",
    "                ret+=dp[i]\n",
    "                ret%=mod\n",
    "        print(dp)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "        d = [0] * delay\n",
    "        f = [0] * (forget - delay)\n",
    "        d[0] = 1\n",
    "        for i in range(1, n):\n",
    "            # tmp = sum(f) # 传染期将在下1天新增这么多人\n",
    "            f[1:] = f[:-1] # 传染期往后顺延1天\n",
    "            f[0] = d[-1] # 传染期第1天由潜伏期最后1天转变过来\n",
    "            d[1:] = d[:-1] # 潜伏期往后顺延1天\n",
    "            d[0] = sum(f)\n",
    "            num = sum(d) + sum(f)\n",
    "        return num % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "\n",
    "        f = [0] * (n + 1)\n",
    "        g = [0] * (n + 1)\n",
    "        f[1], g[1] = 1, 1\n",
    "\n",
    "        for i in range(2, n+1):\n",
    "            l = max(0, i - forget)\n",
    "            r = max(0, i - delay)\n",
    "            f[i] = (g[r] - g[l] + mod) % mod\n",
    "            g[i] = (g[i-1] + f[i]) % mod\n",
    "        \n",
    "        return (g[n] - g[max(0, n - forget)] + mod) % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        f = [0] * n\n",
    "        f[0] = 1\n",
    "        f[1] = -1\n",
    "        ans = 0\n",
    "        cur = 0\n",
    "        for i, v in enumerate(f):\n",
    "            cur = (cur + v) % MOD\n",
    "            if i+forget>=n:\n",
    "                ans = (ans + cur) % MOD\n",
    "            if i + delay < n:\n",
    "                f[i+delay] = (f[i+delay] + cur) % MOD\n",
    "                if i+forget < n:\n",
    "                    f[i+forget] = (f[i+forget] - cur) % MOD\n",
    "        return ans % MOD\n",
    "            \n",
    "\n",
    "\n",
    "# 作者：灵茶山艾府\n",
    "# 链接：https://leetcode.cn/problems/number-of-people-aware-of-a-secret/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "        mod = int(1e9+7)\n",
    "        alive_amount = 1\n",
    "        spread_amount = 0\n",
    "        spread_incr_amount = {1+delay: 1}\n",
    "        dead_amount = {1+forget: 1}\n",
    "        for i in range(2, n+1):\n",
    "            s_num_incr =  spread_incr_amount.get(i) if spread_incr_amount.get(i) != None else 0\n",
    "            d_num_desc = dead_amount.get(i) if dead_amount.get(i) != None else 0\n",
    "            spread_amount += s_num_incr\n",
    "            spread_amount -= d_num_desc\n",
    "            alive_amount += spread_amount - d_num_desc\n",
    "            alive_amount %= mod\n",
    "            spread_incr_amount[i+delay] = spread_amount\n",
    "            dead_amount[i+forget] = spread_amount\n",
    "        return alive_amount\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "        # dp[i]的含义是第i天获取秘密的人\n",
    "        dp = [0] * (n+1)\n",
    "        dp[1] = 1\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(i+delay,i+forget):\n",
    "                if j <= n:\n",
    "                    dp[j] += dp[i]\n",
    "        result = 0\n",
    "        for i in range(n+1-forget,n+1):\n",
    "            result += dp[i]\n",
    "            result %= (10**9+7)\n",
    "        return result%(10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "        dp, m = defaultdict(int), 10 ** 9 + 7\n",
    "        dp[1] = 1\n",
    "        for i in range(2, n+1):\n",
    "            dp[i] = (dp[i-1] + dp[i-delay] - dp[i-forget]) % m\n",
    "        return (dp[n] - dp[n-forget]) % m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "        state = [1] + [0] * (n-1)\n",
    "        pre = 1\n",
    "        for i in range(0, n):\n",
    "            for j in range(i+delay, i + forget):\n",
    "                if j < n:\n",
    "                    state[j] += state[i]\n",
    "                else:\n",
    "                    break\n",
    "                    \n",
    "            \n",
    "        ans = 0\n",
    "        for i in range(n - forget, n):\n",
    "            ans += state[i]\n",
    "        return ans % (10 ** 9 + 7)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        f = [0] * n\n",
    "        f[0] = 1\n",
    "        f[1] = -1\n",
    "        ans = 0\n",
    "        cur = 0\n",
    "        for i, v in enumerate(f):\n",
    "            cur += v\n",
    "            if i+forget>=n:\n",
    "                ans += cur\n",
    "            if i + delay < n:\n",
    "                f[i+delay] += cur\n",
    "                if i+forget < n:\n",
    "                    f[i+forget] -= cur\n",
    "        return ans % MOD\n",
    "            \n",
    "\n",
    "\n",
    "# 作者：灵茶山艾府\n",
    "# 链接：https://leetcode.cn/problems/number-of-people-aware-of-a-secret/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        # dp哈希表，dp[i]表示在已经知道了秘密i天的人数\n",
    "        # dp初始化：一开始只有1个人知道了秘密，且已经过去了0天\n",
    "        dp = {0:1}\n",
    "        # 考虑每一天的情况\n",
    "        for _ in range(n):\n",
    "            new_dp = defaultdict(int)\n",
    "            for k, v in dp.items():\n",
    "                if k < delay:\n",
    "                    new_dp[k+1] = (new_dp[k+1] + dp[k]) % MOD\n",
    "                elif delay <= k < forget:\n",
    "                    new_dp[k+1] = (new_dp[k+1] + dp[k]) % MOD\n",
    "                    new_dp[1] = (new_dp[1] + dp[k]) % MOD\n",
    "                else:\n",
    "                    continue\n",
    "            dp = new_dp\n",
    "        return sum(new_dp.values()) % MOD\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "        dp = [0]*n \n",
    "        dp[0] = 1\n",
    "        for i in range(n):\n",
    "            if(i+delay < n):\n",
    "                for j in range(i+delay,min(i+forget,n)):\n",
    "                    dp[j] += dp[i]\n",
    "        result = 0\n",
    "        for i in range(n-forget,n):\n",
    "            result += dp[i]\n",
    "        return result % (10**9+7)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "kmod = 10**9 + 7\n",
    "class Solution:\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "        res = 1\n",
    "        d = defaultdict(int)\n",
    "        for i in range(1 + delay, 1 + forget):\n",
    "            d[i] = 1\n",
    "        f = defaultdict(int)\n",
    "        f[1 + forget] = 1\n",
    "        for i in range(1 + delay, n + 1):\n",
    "            a, b = d[i], f[i]\n",
    "            res += a - b\n",
    "            res %= kmod\n",
    "            for j in range(i + delay, i + forget):\n",
    "                d[j] += a\n",
    "                d[j] %= kmod\n",
    "            f[i + forget] = a\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "        old_sum = 0\n",
    "        new_sum = 1\n",
    "        ret = 1\n",
    "        old = deque()\n",
    "        new = deque([[1, delay]])\n",
    "        diff = forget - delay\n",
    "        MOD = 10 ** 9 + 7\n",
    "        for i in range(1, n):\n",
    "            if old and old[0][1] == i:\n",
    "                x = old.popleft()\n",
    "                old_sum = (old_sum - x[0]) % MOD\n",
    "            if new and new[0][1] == i:\n",
    "                x = new.popleft()\n",
    "                old_sum = (old_sum + x[0]) % MOD\n",
    "                old.append([x[0], x[1] + diff])\n",
    "                new_sum = (new_sum - x[0]) % MOD\n",
    "            \n",
    "            if old_sum:\n",
    "                # ret = (ret + tot) % MOD\n",
    "                new.append([old_sum, i + delay])\n",
    "                new_sum = (new_sum + old_sum) % MOD\n",
    "            # print(i, new, old, tot, ret)\n",
    "        return (old_sum + new_sum) % MOD\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "        f = [0]*(n)\n",
    "        f[0] = 1\n",
    "        cnt_b = 0\n",
    "        for i,v in enumerate(f):\n",
    "            # 不能产生多余利息的钱\n",
    "            if i+delay >= n:\n",
    "                cnt_b += v\n",
    "            # 能产生多余利息的钱\n",
    "            for j in range(i+delay,min(i+forget,n)):\n",
    "                f[j] = (f[j] + v)\n",
    "        return (f[-1]+cnt_b)%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "        dp=[0]*(n+1)\n",
    "        dp[1]=1\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(i+delay,i+forget):\n",
    "                if j<=n:\n",
    "                    dp[j]+=dp[i]\n",
    "        result=0\n",
    "        for i in range(n+1-forget,n+1):\n",
    "                        result+=dp[i]\n",
    "                        result%=(10**9+7)\n",
    "        return result%(10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "        dp = [0] * (n+1)\n",
    "        dp[1] = 1\n",
    "        result = 0\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(i+delay, i+forget):\n",
    "                if j <= n:\n",
    "                    dp[j] += dp[i]\n",
    "\n",
    "        for i in range(n+1-forget, n+1):\n",
    "            result += dp[i]\n",
    "        return result % (10**9+7)\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "        f = [0]*(n+1)\n",
    "        f[1] = 1\n",
    "        cnt_b = 0\n",
    "        for i in range(1,n+1):\n",
    "            # 不能产生多余利息的钱\n",
    "            if i+delay > n:\n",
    "                cnt_b += f[i]\n",
    "            # 能产生多余利息的钱\n",
    "            for j in range(i+delay,min(i+forget,n+1)):\n",
    "                f[j] = (f[j] + f[i])\n",
    "        return (f[-1]+cnt_b)%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "        MOD = 10**9+7\n",
    "        dp = [[0]*3 for _ in range(n+1)]\n",
    "        # 总， 新，删\n",
    "        dp[1][0],dp[1][1],dp[1][2] = 1,1,0\n",
    "        for i in range(2, n+1):\n",
    "            if i>forget:\n",
    "                dp[i][2] = dp[i-forget][1]\n",
    "            total = dp[i-1][0]\n",
    "            end = max(i-delay, 0)\n",
    "            for j in range(i-1, end, -1):\n",
    "                total -= dp[j][1]\n",
    "\n",
    "            dp[i][1] = total-dp[i][2]\n",
    "            dp[i][0] = dp[i-1][0] - dp[i][2] + total-dp[i][2]\n",
    "        return dp[-1][0]%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "        # dp[i] 的含义是第 i 天获取秘密的人\n",
    "        dp = [0] * (n + 1)\n",
    "        dp[1] = 1\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(i + delay, i + forget):\n",
    "                if j <= n:\n",
    "                    dp[j] += dp[i]\n",
    "        result = 0\n",
    "        for i in range(n + 1 - forget, n + 1):\n",
    "            result += dp[i]\n",
    "            result %= (10**9+7)\n",
    "        return result % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "        dp = [0]*n \n",
    "        dp[0] = 1\n",
    "        for i in range(n):\n",
    "            if(i+delay < n):\n",
    "                for j in range(i+delay,min(i+forget,n)):\n",
    "                    dp[j] += dp[i]\n",
    "        result = 0\n",
    "        for i in range(n-forget,n):\n",
    "            result += dp[i]\n",
    "        return result % (10**9+7)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        dp = [0] * (n+1) # 第i天新获得秘密的人数\n",
    "        dp[1] = 1\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(i+delay, i+forget):\n",
    "                if j <= n:\n",
    "                    dp[j] += dp[i]\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(n+1-forget, n+1):\n",
    "            res += dp[i]\n",
    "            res %= MOD\n",
    "        \n",
    "        return int(res%(MOD))\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "        # f[i]表示第i天会分享秘密的人\n",
    "        # cnt表示第i天不会分享秘密的人\n",
    "        # 初始化\n",
    "        mod = 10**9+7\n",
    "        f = [0]*n \n",
    "        f[0] = 1\n",
    "        cnt = 0\n",
    "        for i in range(n):\n",
    "            if i + delay >= n:\n",
    "                cnt += f[i]\n",
    "            for j in range(i+delay,min(i+forget,n)):\n",
    "                f[j] += f[i]\n",
    "        return (f[n-1]+cnt)%(mod)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:\n",
    "        diff=[0]*(2*n-1)\n",
    "        diff[1]=1\n",
    "        ans=0\n",
    "        for i in range(1,n):\n",
    "            if diff[i]>0:\n",
    "                k=diff[i]\n",
    "                for j in range(i+delay,i+forget):\n",
    "                    diff[j]+=k\n",
    "                if i+forget>n:\n",
    "                    ans+=k\n",
    "        ans+=diff[n]\n",
    "        return ans%(10**9+7)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
